
//1498.满足条件的子序列数目
class Solution {
    #define MOD 1000000007
public:
    int numSubseq(vector<int>& nums, int target) {
        //使用双指针进行处理
        //先进行预处理来记录每一个2的幂次方
        int n=nums.size();
        vector<int> two(n);
        two[0]=1;
        for(int i=1;i<n;i++) two[i]=2*two[i-1]%MOD;

        sort(nums.begin(),nums.end());
        int left=0,right=nums.size()-1;
        int ret=0;
        while(left<=right)  //注意：此处可以相等，left一个也可以组成子数组
        {
            if(nums[left]+nums[right]>target) right--;
            else 
            {
                //此时left与(left,right]区间内任意的子数组都可以形成满足条件的子数组
                ret=(ret+two[right-left])%MOD;
                left++;
            }
        }
        return ret;
    }
};